package xyz.vopen.leetcode.q300;

import java.util.Arrays;

/**
 * {@link ElveXu}
 *
 * @author <a href="mailto:iskp.me@gmail.com">Elve.Xu</a>
 * @version ${project.version} - 2020-04-28.
 */
public class ElveXu {

  public static void main(String[] args) {

    long start = System
        .currentTimeMillis();
    int[] test = {29, 3, 4, 5, 7, 10, 111, 203};
    System.out.println(execute(test) + ", " + (System.currentTimeMillis() - start));
  }

  static int execute(int[] nums) {

    if (nums == null || nums.length == 0) {
      return 0;
    }

    int len = nums.length;

    int[] target = new int[len];

    Arrays.fill(target, 1);

    for (int i = 0; i < len; i++) {
      for (int j = 0; j < i; j++) {
        target[i] = Math.max(target[i], nums[i] > nums[j] ? target[j] + 1 : 1);
      }
    }

    return Arrays.stream(target).max().getAsInt();
  }
}
